package wangn.procedure;

import wangn.adt.CFG;
import wangn.adt.base.More;

import java.util.List;

/**
 * 求FIRST
 *
 * 语法定义：@是S'    %是epsilon   大写字母是非终结符   其它均为终结符
 *
 * 步骤：
 * 一、判断传入的flags，若空就直接返回，否则取第一个字符如X，计算FIRST(X)
 * 二、若X为终结符就将X加入FIRST(X)
 * 三、若X->%,将%加入FIRST（X)
 * 四、若X非终结符，且有X->Y1Y2...Yn，则
 */
public class FIRST {

    private static CFG cfg;

    public static More<Character> first(CFG cfgIn, String flags){
        cfg = cfgIn;
        More<Character> more = new More<>();
        if (flags.equals(""))return more;
        int i = 0;
        while (i < flags.length()){
            char x = flags.charAt(i);
            More<Character> characterMore = firstChar(x);
            unionCharsWithoutEpsilon(more,characterMore);
            if (!characterMore.containsKey('%'))return more;//如果不包含epsilon就直接退出
            i++;
        }
        more.addItem('%');//如果都包含epsilon就加进去
        return more;
    }

    private static More<Character> first(String flags){
        return first(cfg,flags);
    }

    private static More<Character> firstChar(char c){
        More<Character> reMore = new More<>();
        if (isVn(c)){
            List<Integer> sameLeftCharList = cfg.findSameLeftProducts(c+"");
            for (int i : sameLeftCharList){
                String rightGrammar = cfg.getGrammar(i).getSecond();
                More<Character> tmpMore = first(rightGrammar);
                unionChars(reMore,tmpMore);
            }
        }else{
            reMore.addItem(c);
        }
        return reMore;
    }

    private static boolean isVn(char c){
        return c>='A'&&c<='Z';
    }

    private static void unionCharsWithoutEpsilon(More<Character> more1, More<Character> more2){
        List<Character> list = more2.getAllItems();
        for (char c : list){
            if (c!='%'&&!more1.containsKey(c)){
                more1.addItem(c);
            }
        }
    }

    private static void unionChars(More<Character> more1, More<Character> more2){
        List<Character> list = more2.getAllItems();
        for (char c : list){
            if (!more1.containsKey(c)){
                more1.addItem(c);
            }
        }
    }
}
